package com.sicheng.algorithm.广度优先;

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/5/20 18:02
 */
public class 走迷宫升级版 {
    /**
     * 走迷宫升级版——边的权值不同
     * 单点时限: 2.0 sec
     * 内存限制: 256 MB
     * 一天，sunny 不小心进入了一个迷宫，不仅很难寻找出路，而且有的地方还有怪物，但是 sunny 有足够的能力杀死怪物，
     * 但是需要一定的时间，但是 sunny 想早一点走出迷宫，所以请你帮助他计算出最少的时间走出迷宫，输出这个最少时间。
     * <p>
     * 我们规定每走一格需要时间单位 1, 杀死怪物也需要时间 1,
     * 如果不能走到出口，则输出 impossible. 每次走只能是上下左右 4 个方向。
     * <p>
     * 输入格式
     * 每次首先 2 个数 n,m (0<n,m≤200)，代表迷宫的高和宽，然后 n 行，每行 m 个字符。
     * <p>
     * S 代码你现在所在的位置。
     * T 代表迷宫的出口。
     * # 代表墙，你是不能走的。
     * X 代表怪物。
     * . 代表路，可以走。
     * 处理到文件结束。
     * <p>
     * 输出格式
     * 输出最少的时间走出迷宫。不能走出输出 impossible。
     * <p>
     * 样例
     * 输入样例：
     * 4 4
     * S.X.
     * #..#
     * ..#.
     * X..T
     * 4 4
     * S.X.
     * #..#
     * ..#.
     * X.#T
     * 输出样例：
     * 6
     * impossible
     * <p>
     * https://www.acwing.com/solution/content/2078/
     */

    static int n, m;
    static char[][] g = new char[200][200];//存储迷宫
    static int x, y, X, Y;//起点终点
    static PriorityQueue<int[]> queue = new PriorityQueue<>(Comparator.comparingInt(e -> e[2]));

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextInt()) {
            n = scanner.nextInt();
            m = scanner.nextInt();
            for (int i = 0; i < n; i++) {
                String next = scanner.next();
                for (int j = 0; j < next.length(); j++) {
                    g[i][j] = next.charAt(j);
                    if (g[i][j] == 'S') {
                        x = i;
                        y = j;
                    } else if (g[i][j] == 'T') {
                        X = i;
                        Y = j;
                    }
                }
            }
            int res = bfs();
            if (res > 0) {
                System.out.println(res);
            } else {
                System.out.println("impossible");
            }
        }
    }

    static int[][] d = {
            {1, 0},
            {-1, 0},
            {0, 1},
            {0, -1}
    };

    private static int bfs() {
        int[] start = {x, y, 0};
        g[x][y] = '#';
        queue.offer(start);
        while (!queue.isEmpty()) {
            int[] e = queue.poll();
            for (int[] ints : d) {
                int x = e[0] + ints[0];
                int y = e[1] + ints[1];
                int dist = e[2];
                if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] != '#') {
                    if (g[x][y] == '.')
                        queue.offer(new int[]{x, y, dist + 1});
                    else if (g[x][y] == 'X')
                        queue.offer(new int[]{x, y, dist + 2});
                    else if (g[x][y] == 'T') {
                        queue.clear();
                        return dist + 1;
                    }
                    g[x][y] = '#';

                }

            }


        }
        return -1;
    }
}
